【题解】 [六省联考2017]分手是祝愿概率DP loj2145

概率神仙题的传送门：~~别戳偏了~~

设 $f_i$ 表示还剩下 $i$ 盏灯亮到还剩下 $i-1$ 盏灯亮的期望操作次数，这个时候有 $\frac{i}{n}$ 的概率按中亮的，但是没有按中亮的的话就只能退到 $f_{i+1}$ 。不难列出转移方程：

$f_i=\frac{i}{n}+(1-\frac{i}{n})\cdot (1+f_i+f_{i+1})$

因为转移式中有个 $f_i$ ，有些不好办……推一推式子康康。

$f_i=\frac{i}{n}+1\cdot (1+f_i+f_{i+1})-\frac{i}{n}\cdot (1+f_i+f_{i+1})\\\\f_i=\frac{i}{n}+1+f_i+f_{i+1}-\frac{i}{n}-\frac{i}{n}f_i-\frac{i}{n}f_{i+1}\\\\f_i=1+f_i+f_{i+1}-\frac{i}{n}f_i-\frac{i}{n}f_{i+1}\\\\\frac{i}{n}f_i=1+f_{i+1}-\frac{i}{n}f_{i+1}\\\\f_i=\frac{1+f_{i+1}-\frac{i}{n}f_{i+1}}{\frac{i}{n}}\\\\f_i=\frac{n\cdot(1+f_{i+1})-i\cdot f_{i+1}}{i}\\\\f_i=\frac{n+(n-i)\cdot f_{i+1}}{i}\\\\f_i=1+\frac{(n-i)\cdot (f_{i+1}+1)}{i}$

预处理逆元就可以直接计算了，记得最后乘上 $n!$ 。

Code:

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+7;
const int inf=1e9+9;
const int p=100003;

int n,k,step,a[N];
long long ans,f[N],inv[N];
vector<int> g[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int main() {
    IN(n),IN(k);
    inv[0]=0,inv[1]=1;
    for(int i=2;i<=n;++i) inv[i]=(long long)(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;++i) IN(a[i]);
    for(int i=1;i<=n;++i) for(int j=i;j<=n;j+=i) g[j].push_back(i);
    for(int i=n;i>=1;--i) if(a[i]) {
        for(int j=0;j<g[i].size();++j) a[g[i][j]]^=1;
        ++step;
    }
    if(step<=k) ans=step;
    else {
        f[n]=1;
        for(int i=n-1;i>1;--i) f[i]=(1ll+(1ll*n-i)*(f[i+1]+1)*inv[i])%p;
        for(int i=step;i>k;--i) ans=(ans+f[i])%p;
        ans=(ans+k)%p;
    }
    for(int i=1;i<=n;++i) ans=(1ll*i*ans)%p;
    printf("%lld\n",ans);
    return 0;
}

本文标题:【题解】 [六省联考2017]分手是祝愿概率DP loj2145

文章作者:Qiuly

发布时间:2019年05月05日 - 00:00

最后更新:2019年05月05日 - 10:43

原始链接:http://qiulyblog.github.io/2019/05/05/[题解]loj2145/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。